#https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5
class Solution {
public:
void InOrder(TreeNode* cur ,TreeNode*& prev)
{
	if(cur == nullptr)
		return ;
	InOrder(cur->left, prev);
	
	//处理链接, left:相当于prev指针 right :相当于next指针
	cur->left = prev;
	if(prev != nullptr)
	{
		prev->right = cur;
	}
	prev = cur;

	InOrder(cur->right, prev);
}
TreeNode* Convert(TreeNode* root) {
	if(root == nullptr)
		return root;
	TreeNode* prev = nullptr;
	InOrder(root,prev);
	
	TreeNode* head = root;
	while(head->left)
	{
		head = head->left;
	}
	return head;
}
};

#https://www.nowcoder.com/practice/d9820119321945f588ed6a26f0a6991f
TreeNode* process(TreeNode* root,int p,int q)
{
    if(root == nullptr) 
        return nullptr;
    if(root->val > p && root->val > q)
        return process(root->left,p,q);
    else if(root->val < p && root->val < q)
        return process(root->right,p,q);
    else
        return root;
}
int lowestCommonAncestor(TreeNode* root, int p, int q) {
    // write code here
    return process(root,p,q)->val;
}
